package com.example.bst;

/**
 * @Description 最大二叉搜索子树问题
 * @Date 2022/4/6
 * @Created by Jonathan
 */
public class MaxSubBSTSize {
    static class Node {
        Integer value;
        Node right;
        Node left;
    }

    static class Info {
        boolean isBST;
        int maxSubBSTSize;
        int min;
        int max;

        public Info(boolean isBST, int maxSubBSTSize, int min, int max) {
            this.isBST = isBST;
            this.maxSubBSTSize = maxSubBSTSize;
            this.min = min;
            this.max = max;
        }
    }

    /**
     * @param head 头节点
     */
    private Info process(Node head) {
        // base case
        if (head == null)
            return null;
        // 递归处理
        Info left = process(head.left);
        Info right = process(head.right);

        boolean isBST = false;
        int maxSubBSTSize = 0;
        // 初始化
        int max = head.value;
        int min = head.value;

        if (left != null) {
            min = left.min;
            max = left.max;
            maxSubBSTSize = left.maxSubBSTSize;
        }

        if (right != null) {
            min = Math.min(min, right.min);
            max = Math.max(max, right.max);
            maxSubBSTSize = Math.max(maxSubBSTSize, right.maxSubBSTSize);
        }

        // 如果左边是 右边也是
        // 左边的最大值小于head的值
        // 右边的最小值大于head的值
        // 考虑null的情况
        if (left == null ? true : left.isBST
                && right == null ? true : right.isBST
                && left == null ? true : left.max < head.value
                && right == null ? true : head.value < right.min) {
            isBST = true;
            maxSubBSTSize = (left == null ? 0 : left.maxSubBSTSize)
                    + (right == null ? 0 : right.maxSubBSTSize)
                    + 1;
        }
        return new Info(isBST, maxSubBSTSize, min, max);
    }

}
